package com.zdp.leetcodeMiddle;
import com.zdp.util.ListNode;

import java.util.ArrayList;
import java.util.List;

/*
* 给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 链表求和_02_05 {
    public static void main(String[] args) {
        链表求和_02_05 demo = new 链表求和_02_05();
        ListNode listNode = ListNode.createListNode(7, 1, 6);
        ListNode listNode1 = ListNode.createListNode(5, 9, 2);
        ListNode listNode2 = demo.addTwoNumbers(listNode, listNode1);
        ListNode.staticSoutList(listNode2);
    }

    /*
    * 逆序添加，用 一个进位暂存即可
    * */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int temp = 0;
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode head = new ListNode();
        ListNode tail = head;
        while(p1 != null && p2 != null){
            int tt = p1.val + p2.val + temp;
            temp = tt /10;
            ListNode t = new ListNode(tt%10);
            // 插入
            t.next = tail.next;
            tail.next = t;
            tail =t;
            p1 = p1.next;
            p2 = p2.next;
        }
        // 判断是否有链表长度不等的情况
        while(p1!=null){
            // p1 长
            int tt = p1.val + temp;
            temp = tt / 10;
            ListNode t = new ListNode (tt%10);
            t.next = tail.next;
            tail.next = t;
            tail = t;
            p1 = p1.next;
        }
        while(p2!=null){
            // p2 长
            int tt = p2.val + temp;
            temp = tt / 10;
            ListNode t = new ListNode (tt%10);
            t.next = tail.next;
            tail.next = t;
            tail = t;
            p2 = p2.next;
        }
        //  判断是否还有进位
        if(temp > 0 ){
            // 有进位
            ListNode t = new ListNode(temp);
            t.next = tail.next;
            tail.next = t;
        }
        return head.next;
    }

    /*
    * 正序如何实现
    *  用数组 暂存相加的结果
    * */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2){
        List<Integer> list = new ArrayList<>();
        list.add(0); // 存放首位的进位
        ListNode p1 = l1;
        ListNode p2 = l2;
        while(p1!=null && p2!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        if(p1 == null){ // l1 比较短
            p1 = l2;
            while(p2 != null){
                p2 = p2.next;
                list.add(p1.val);
                p1 = p1.next;
            }
            p2 = p1;
            p1 = l1;
        }else if(p2 == null){
            // l2 比较短
            p2 = l1;
            while(p1 != null){
                p1 = p1.next;
                list.add(p2.val);
                p2 = p2.next;
            }
            p1 = p2;
            p2 = l2;
        }
        while(p1!=null && p2 !=null){
            list.add(p1.val + p2.val);
            p1 = p1.next;
            p2 = p2.next;
        }
        // 处理
        ListNode head = new ListNode();
        ListNode tail = head;
        for(int i=list.size()-1; i >0 ; i--){
            // 处理一下进位吧
            list.set(i-1,list.get(i-1) + list.get(i)/10);
            list.set(i,list.get(i)%10);
        }
        // 处理前缀0
        int j =0;
        while(list.get(j) ==0 && j < list.size()-1){
            j++;
        }
        for(int i=j;i<list.size() ; i++){
            // 填充到链表
            ListNode  tt = new ListNode(list.get(i));
            tt.next = tail.next;
            tail.next = tt;
            tail = tt;
        }
        return head.next;
    }
}
